package master;

import java.util.List;

/**
 * 分隔链表
 *
 * @author chenyw
 * @date 2022/8/1 10:43
 */
public class M86partition {

    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }

/*    //题干没完全理解透， 直接从头便利就行不会改变原有节点的相对位置
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        while (p != null) {
            if (p.val >= x) {
                break;
            }
            pre = p;
            p = p.next;
        }
        if (p == null) {
            return head;
        }
        ListNode bigHead = p;
        ListNode bigTail = p;
        p = p.next;
        ListNode smallHead = p, smallTail = head;
        boolean isFirst = true;
        while (p != null) {
            if (p.val < x) {
                if (isFirst) {
                    smallHead = p;
                    smallTail = p;
                    isFirst = false;
                } else {
                    smallTail.next = p;
                    smallTail = p;
                }
            } else {
                bigTail.next = p;
                bigTail = p;
            }
            p = p.next;
        }
        if (isFirst) {
            return head;
        }
        pre.next = smallHead;
        smallTail.next = bigHead;
        bigTail.next = null;
        return dummyNode.next;
    }*/
}
